home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / essen.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  4.2 KB  |  171 lines  |  [TEXT/R*ch]
  1. /*
  2.     module: essen.c
  3.     purpose: Find essential primes in a multiple-valued function
  4. */
  5.  
  6. #include "espresso.h"
  7.  
  8. /*
  9.     essential -- return a cover consisting of the cubes of F which are
  10.     essential prime implicants (with respect to F u D); Further, remove
  11.     these cubes from the ON-set F, and add them to the OFF-set D.
  12.  
  13.     Sometimes EXPAND can determine that a cube is not an essential prime.
  14.     If so, it will set the "NONESSEN" flag in the cube.
  15.  
  16.     We count on IRREDUNDANT to have set the flag RELESSEN to indicate
  17.     that a prime was relatively essential (i.e., covers some minterm
  18.     not contained in any other prime in the current cover), or to have
  19.     reset the flag to indicate that a prime was relatively redundant
  20.     (i.e., all minterms covered by other primes in the current cover).
  21.     Of course, after executing irredundant, all of the primes in the
  22.     cover are relatively essential, but we can mark the primes which
  23.     were redundant at the start of irredundant and avoid an extra check
  24.     on these primes for essentiality.
  25. */
  26.  
  27. pcover essential(Fp, Dp)
  28. IN pcover *Fp, *Dp;
  29. {
  30.     register pcube last, p;
  31.     pcover E, F = *Fp, D = *Dp;
  32.  
  33.     /* set all cubes in F active */
  34.     (void) sf_active(F);
  35.  
  36.     /* Might as well start out with some cubes in E */
  37.     E = new_cover(10);
  38.  
  39.     foreach_set(F, last, p) {
  40.     /* don't test a prime which EXPAND says is nonessential */
  41.     if (! TESTP(p, NONESSEN)) {
  42.         /* only test a prime which was relatively essential */
  43.         if (TESTP(p, RELESSEN)) {
  44.         /* Check essentiality */
  45.         if (essen_cube(F, D, p)) {
  46.             if (debug & ESSEN)
  47.             printf("ESSENTIAL: %s\n", pc1(p));
  48.             E = sf_addset(E, p);
  49.             RESET(p, ACTIVE);
  50.             F->active_count--;
  51.         }
  52.         }
  53.     }
  54.     }
  55.  
  56.     *Fp = sf_inactive(F);               /* delete the inactive cubes from F */
  57.     *Dp = sf_join(D, E);        /* add the essentials to D */
  58.     sf_free(D);
  59.     return E;
  60. }
  61.  
  62. /*
  63.     essen_cube -- check if a single cube is essential or not
  64.  
  65.     The prime c is essential iff
  66.  
  67.     consensus((F u D) # c, c) u D
  68.  
  69.     does not contain c.
  70. */
  71. bool essen_cube(F, D, c)
  72. IN pcover F, D;
  73. IN pcube c;
  74. {
  75.     pcover H, FD;
  76.     pcube *H1;
  77.     bool essen;
  78.  
  79.     /* Append F and D together, and take the sharp-consensus with c */
  80.     FD = sf_join(F, D);
  81.     H = cb_consensus(FD, c);
  82.     free_cover(FD);
  83.  
  84.     /* Add the don't care set, and see if this covers c */
  85.     H1 = cube2list(H, D);
  86.     essen = ! cube_is_covered(H1, c);
  87.     free_cubelist(H1);
  88.  
  89.     free_cover(H);
  90.     return essen;
  91. }
  92.  
  93.  
  94. /*
  95.  *  cb_consensus -- compute consensus(T # c, c)
  96.  */
  97. pcover cb_consensus(T, c)
  98. register pcover T;
  99. register pcube c;
  100. {
  101.     register pcube temp, last, p;
  102.     register pcover R;
  103.  
  104.     R = new_cover(T->count*2);
  105.     temp = new_cube();
  106.     foreach_set(T, last, p) {
  107.     if (p != c) {
  108.         switch (cdist01(p, c)) {
  109.         case 0:
  110.             /* distance-0 needs special care */
  111.             R = cb_consensus_dist0(R, p, c);
  112.             break;
  113.  
  114.         case 1:
  115.             /* distance-1 is easy because no sharping required */
  116.             consensus(temp, p, c);
  117.             R = sf_addset(R, temp);
  118.             break;
  119.         }
  120.     }
  121.     }
  122.     set_free(temp);
  123.     return R;
  124. }
  125.  
  126.  
  127. /*
  128.  *  form the sharp-consensus for p and c when they intersect
  129.  *  What we are forming is consensus(p # c, c).
  130.  */
  131. pcover cb_consensus_dist0(R, p, c)
  132. pcover R;
  133. register pcube p, c;
  134. {
  135.     int var;
  136.     bool got_one;
  137.     register pcube temp, mask;
  138.     register pcube p_diff_c=cube.temp[0], p_and_c=cube.temp[1];
  139.  
  140.     /* If c contains p, then this gives us no information for essential test */
  141.     if (setp_implies(p, c)) {
  142.     return R;
  143.     }
  144.  
  145.     /* For the multiple-valued variables */
  146.     temp = new_cube();
  147.     got_one = FALSE;
  148.     INLINEset_diff(p_diff_c, p, c);
  149.     INLINEset_and(p_and_c, p, c);
  150.  
  151.     for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
  152.     /* Check if c(var) is contained in p(var) -- if so, no news */
  153.     mask = cube.var_mask[var];
  154.     if (! setp_disjoint(p_diff_c, mask)) {
  155.         INLINEset_merge(temp, c, p_and_c, mask);
  156.         R = sf_addset(R, temp);
  157.         got_one = TRUE;
  158.     }
  159.     }
  160.  
  161.     /* if no cube so far, add one for the intersection */
  162.     if (! got_one && cube.num_binary_vars > 0) {
  163.     /* Add a single cube for the intersection of p and c */
  164.     INLINEset_and(temp, p, c);
  165.     R = sf_addset(R, temp);
  166.     }
  167.  
  168.     set_free(temp);
  169.     return R;
  170. }
  171.